class Solution(object):
    def candyCrush(self, board):
        """
        :type board: List[List[int]]
        :rtype: List[List[int]]
        """
        m = len(board)
        n = len(board[0])
        zero_grid = set()
        for i in range(m):
            left_index = 0
            last_value = -1
            right_index = 0
            while right_index < n:
                if board[i][right_index] == 0:
                    last_value = -1
                    left_index = right_index + 1
                else:
                    if last_value == -1:
                        left_index = right_index
                        last_value = board[i][right_index]
                    else:
                        if board[i][right_index] == last_value:
                            if right_index - left_index == 2:
                                for k in range(left_index, right_index + 1):
                                    zero_grid.add((i, k))
                            else:
                                if right_index - left_index > 2:
                                    zero_grid.add((i, right_index))
                        else:
                            last_value = board[i][right_index]
                            left_index = right_index
                right_index += 1
        for j in range(n):
            left_index = 0
            last_value = -1
            right_index = 0
            while right_index < m:
                if board[right_index][j] == 0:
                    last_value = -1
                    left_index = right_index + 1
                else:
                    if last_value == -1:
                        left_index = right_index
                        last_value = board[right_index][j]
                    else:
                        if board[right_index][j] == last_value:
                            if right_index - left_index == 2:
                                for k in range(left_index, right_index + 1):
                                    zero_grid.add((k, j))
                            else:
                                if right_index - left_index > 2:
                                    zero_grid.add((right_index, j))
                        else:
                            last_value = board[right_index][j]
                            left_index = right_index
                right_index += 1
        if not zero_grid:
            return board
        for x, y in zero_grid:
            board[x][y] = 0
        for j in range(n):
            zero_count = 0
            index = m - 1
            while index >= 0:
                if board[index][j] == 0:
                    zero_count += 1
                else:
                    if zero_count > 0:
                        board[index + zero_count][j] = board[index][j]
                        board[index][j] = 0
                index -= 1
        return self.candyCrush(board)

data = Solution()
board = [[110, 5, 112, 113, 114], [210, 211, 5, 213, 214], [310, 311, 3, 313, 314], [410, 411, 412, 5, 414],
         [5, 1, 512, 3, 3], [610, 4, 1, 613, 614], [710, 1, 2, 713, 714], [810, 1, 2, 1, 1], [1, 1, 2, 2, 2],
         [4, 1, 4, 4, 1014]]
print(data.candyCrush(board))
